package theeg.DependencyAnalysis.Core.Algorithms.SubstringDetection;

import java.util.Stack;

/**
 *
 * @author theeg
 */
public class SuffixTree {

    private final char[] _text;
    private int _nodeCount;

    public char[] getText() {
        return _text;
    }

    private final Node _root;

    public Node getRootNode() {
        return _root;
    }

    public SuffixTree(char[] text) {
        _text = text;
        _root = new Node(this, null);

        Suffix suffixLink = new Suffix(_root, 0, -1);
        for (int i = 0; i < text.length; i++) {
            addPrefix(suffixLink, i);
        }
    }

    public int createNewNodeNumber() {
        return _nodeCount++;
    }

    private void addPrefix(Suffix suffixLink, int endIndex) {
        Node lastParentNode = null;
        Node parentNode;

        while (true) {
            parentNode = suffixLink.originNode;

            if (findMatchingEdge(suffixLink, endIndex, new Node[]{parentNode})) {
                break;
            }

            // We didn't find a matching edge, so we create a new one, add it to the tree at the parent node position,
            // and insert it into the hash table.  When we create a new node, it also means we need to create
            // a suffix link to the new node from the last node we visited.
            lastParentNode = createNewEdge(endIndex, parentNode, lastParentNode);

            // This final step is where we move to the next smaller suffix
            if (_root.equals(suffixLink.originNode)) {
                suffixLink.beginIndex++;
            } else {
                suffixLink.changeOriginNode();
            }
            suffixLink.Canonize();
        }
        updateSuffixNode(lastParentNode, parentNode);
        suffixLink.endIndex++; //Now the endpoint is the next active point
        suffixLink.Canonize();
    }

    private Node createNewEdge(int endIndex, Node parentNode, Node lastParentNode) {
        Edge newEdge = new Edge(endIndex, _text.length - 1, parentNode);
        newEdge.insert();
        updateSuffixNode(lastParentNode, parentNode);
        lastParentNode = parentNode;
        return lastParentNode;
    }

    private boolean findMatchingEdge(Suffix suffixLink, int endIndex, Node[] parentNode) {
        Edge edge;
        if (suffixLink.IsExplicit()) {
            //RULE1
            edge = suffixLink.originNode.findEdge(_text[endIndex]);
            if (edge != null) {
                return true;
            }
        } else {
            //implicit node, a little more complicated
            edge = suffixLink.originNode.findEdge(_text[suffixLink.beginIndex]);
            int span = suffixLink.getSpan();
            //RULE3
            if (_text[edge.beginIndex + span + 1] == _text[endIndex]) {
                return true;
            }
            //RULE2
            parentNode[0] = edge.splitEdge(suffixLink);
        }
        return false;
    }

    private void updateSuffixNode(Node node, Node suffixNode) {
        if (node != null && node != _root) {
            node.suffixNode = suffixNode;
        }
    }

    public CommonSubstring findLongestRepeatition() {
        Stack<Node> visited = new Stack();
        visited.push(_root);
        int maxLength = 0;
        Edge bestCandidate = null;
        while (visited.size() > 0) {
            Node current = visited.pop();
            Edge[] edges = current.getEdges();

            for (Edge edge : edges) {
                if (edge.endIndex + 1 < _text.length && edge.getSpan() > maxLength) {
                    bestCandidate = edge;
                    maxLength = edge.getSpan();
                }
                visited.push(edge.endNode);
            }
        }
        if (bestCandidate == null) {
            return null;
        }
        Edge[] repeatitions = bestCandidate.endNode.getEdges();
        CommonSubstring commonSubstring = new CommonSubstring();

        commonSubstring.length = maxLength + 1;
        commonSubstring.textIndices = new int[repeatitions.length];
        commonSubstring.beginIndices = new int[repeatitions.length];
        commonSubstring.endIndices = new int[repeatitions.length];

        int i = 0;
        for (Edge edge : repeatitions) {
            commonSubstring.beginIndices[i] = edge.beginIndex - commonSubstring.length;
            commonSubstring.endIndices[i] = edge.endIndex - commonSubstring.length;
            i++;
        }
        return commonSubstring;
    }

    public boolean contains(char[] str) {
        return indexOf(str) >= 0;
    }

    public int indexOf(char[] str) {
        if (str.length == 0) {
            return -1;
        }

        int index = -1;
        Node node = _root;

        int i = 0;
        while (i < str.length) {
            if ((node == null) || (i == _text.length)) {
                return -1;
            }

            Edge edge = node.findEdge(str[i]);
            if (edge == null) {
                return -1;
            }

            index = edge.beginIndex - i;
            i++;

            for (int j = edge.beginIndex + 1; j <= edge.endIndex; j++) {
                if (i == str.length) {
                    break;
                }
                if (_text[j] != str[i]) {
                    return -1;
                }
                i++;
            }
            node = edge.endNode;
        }
        return index;
    }
}
